package com.mystudy.leetcode.problem.tree.p_637;

import com.mystudy.leetcode.base.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @program: infoalgorithm
 * @description: 二叉树的层平均值
 * @author: zhouzhilong
 * @create: 2019-07-24 14:29
 **/
public class Solution {

    /**
     * 土鳖做法１
     * @param root
     * @return
     */
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        List<List<Integer>> list = new ArrayList<>();
        levelsOrder(root, 0, list);

        for (List<Integer> integers : list) {
            System.out.println(integers);
            long sum = 0;
            for (Integer integer : integers) {
                sum = sum + integer;
            }
            System.out.println(sum);
            result.add(sum * 1.0 / integers.size());
        }

        return result;
    }

    private void levelsOrder(TreeNode node, int depth, List<List<Integer>> result) {
        if (node == null) {
            return;
        }

        if (depth + 1 > result.size()) {
            result.add(new ArrayList<>());
        }

        result.get(depth).add(node.val);
        levelsOrder(node.left, depth + 1, result);
        levelsOrder(node.right, depth + 1, result);
    }

    /**
     * 土鳖做法2
     * @param root
     * @return
     */
    public List<Double> averageOfLevels2(TreeNode root) {
        List<Double> result = new ArrayList<>();
        Queue<TreeNode> parentQueue = new LinkedList<>();
        Queue<TreeNode> sonQueue = new LinkedList<>();

        parentQueue.offer(root);

        int count = 0;
        long sum = 0L;
        while (!parentQueue.isEmpty()) {
            TreeNode cur = parentQueue.poll();
            if(cur.left != null){
                sonQueue.offer(cur.left);
            }
            if(cur.right != null){
                sonQueue.offer(cur.right);
            }

            sum = sum + cur.val;
            count++;
            if (parentQueue.isEmpty()) {
                result.add(sum * 1.0 / count);
                sum = 0;
                count = 0;
                parentQueue = sonQueue;
                sonQueue = new LinkedList<>();
            }

        }
        return result;
    }


}
